/**  01背包--装满容量j的背包的方法数
返回几种方式--组合

给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，
可以构造一个 表达式 ：例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，
在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1"
输入：nums = [1,1,1,1,1], target = 3
输出：5

nums分为两部分：加数、减数
｜加数x-减数y｜=target
转换背包问题 每个元素只能用一次---01背包--几种方式可以装满背包
分为两组:加数x-减数y

找到sum&target的关系:
[
  x+y=sum;
  x-y=target;
]
==》2*x=sum+target;
数学原理：
如果两个整数的和是奇数，那么它们的差也一定是奇数；
如果两个整数的和是偶数，那么它们的差也一定是偶数。
==》奇数+奇数 = 偶数；偶数+偶数=偶数
==》sum+target必然是偶数

边缘条件：
(1) sum大于等于target
(2) sum+target必然是偶数 

dp[j] 装满容量j的背包的方法数
dp[j]+=dp[j-nums[i]]
values=weights=nums

 */
var findTargetSumWays = function(nums, target) {
  const sum = nums.reduce((a,b)=> a+b);

  //永远到不了target
  if(Math.abs(target)>sum) return 0;
  //
  if((sum+target)%2) return 0;

  //w=加数的个数
  //背包转化，和数就是装下的元素的最大容量，
  const w = (sum+target)/2;

  const dp = Array(w+1).fill(0);

  dp[0]=1; //容量为0的背包有一种方法

  for(let i=0;i<nums.length;i++){
    for(let j=w;j>=nums[i];j--){
      // dp[j] = dp[j] + dp[j-nums[i]];
      dp[j]+=dp[j-nums[i]]
    }
  }
  return dp[w]
};

/**
 * review 1211✅
 */

const nums = [1,1,1,1,1];
const target = 3;
// console.log('目标和',fun(nums, target));